package leetcode;

public class Test0021 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //递归结束条件
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        if(l1.val<l2.val){//l1是最小的节点，则l1应该指向l1后面和l2链表中最小的节点
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
        else {
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        ListNode newNode=null;
//        ListNode newNodeEnd=null;
//        if(l1==null)
//            return l2;
//        if(l2==null)
//            return l1;
//        while (l1 !=null && l2 !=null){
//            if(l1.val<l2.val){
//                if(newNodeEnd!=null)
//                    newNodeEnd.next=l1;//新链表的尾部指向新的节点
//                if(newNode==null)//新链表头部
//                    newNode=l1;
//                newNodeEnd=l1;//更新尾部指针
//
//                l1=l1.next;//走向下一个节点
//            }else {
//                if(newNodeEnd!=null)
//                    newNodeEnd.next=l2;
//                if(newNode==null)
//                    newNode=l2;
//                newNodeEnd=l2;
//                l2=l2.next;
//            }
//        }
//        if(l1!=null){
//            newNodeEnd.next=l1;
//        }
//        if(l2!=null){
//            newNodeEnd.next=l2;
//        }
//
//        return newNode;
//    }
}
